Free lattice

 ( Lattice Theory ) 

In mathematics, in the area of order theory, a free lattice is the free object corresponding to a lattice. As free objects, they have the universal property.

---

Formal definition Because the concept of a lattice can be axiomatised in terms of two operations $\backslash wedge$ and $\backslash vee$ satisfying certain identities, the category of all lattices constitute a variety (universal algebra), and thus there exist (by general principles of universal algebra) within this category: lattices where only those relations hold which follow from the general axioms.

These free lattices may be characterised using the relevant universal property. Concretely, free lattice is a functor $F$ from sets to lattices, assigning to each set $X$ the free lattice $F(X)$ equipped with a set map $\backslash eta\backslash colon\; X\; \backslash longrightarrow\; F(X)$ assigning to each $x\; \backslash in\; X$ the corresponding element $\backslash eta(x)\; \backslash in\; F(X)$. The universal property of these is that there for any map $f\backslash colon\; X\; \backslash longrightarrow\; L$ from $X$ to some arbitrary lattice $L$ exists a unique lattice homomorphism $\backslash tilde\{f\}\backslash colon\; F(X)\; \backslash longrightarrow\; L$ satisfying $f\; =\; \backslash tilde\{f\}\; \backslash circ\; \backslash eta$, or as a commutative diagram: $$$$

 \begin{array}{cccc}
   X & \stackrel{\eta}{\longrightarrow} & F(X) \\
   & \!\forall f \searrow & \Bigg\downarrow\exists_1 \tilde{f} \!\!\!\!\!\!\!\!\!\! &\quad\\
   & & L
 \end{array}
     

The functor $F$ is adjoint functors to the forgetful functor from lattices to their underlying sets.

It is frequently possible to prove things about the free lattice directly using the universal property, but such arguments tend to be rather abstract, so a concrete construction provides a valuable alternative presentation.

---

Semilattices In the case of , an explicit construction of the free semilattice $F\_\backslash vee(X)$ is straightforward to give; this helps illustrate several features of the definition by way of universal property. Concretely, the free semilattice $F\_\backslash vee(X)$ may be realised as the set of all finite nonempty subsets of $X$, with ordinary set union as the join operation $\backslash vee$. The map $\backslash eta\backslash colon\; X\; \backslash longrightarrow\; F\_\backslash vee(X)$ maps elements of $X$ to , i.e., $\backslash eta(x)\; =\; \backslash \{x\backslash \}$ for all $x\; \backslash in\; X$. For any semilattice $L$ and any set map $f\backslash colon\; X\; \backslash longrightarrow\; L$, the corresponding universal morphism $\backslash tilde\{f\}\backslash colon\; F\_\backslash vee(X)\; \backslash longrightarrow\; L$ is given by $$$$

 \tilde{f}(S) = \bigvee_{x \in S} f(x)
 \qquad\text{for all } S \in F_\vee(X)
     

where $\backslash bigvee$ denotes the semilattice operation in $L$.

This form of $\backslash tilde\{f\}$ is forced by the universal property: any $S\; \backslash in\; F\_\backslash vee(X)$ can be written as a finite union of elements on the form $\backslash eta(x)$ for some $x\; \backslash in\; X$, the equality in the universal property says $\backslash tilde\{f\}\backslash bigl(\; \backslash eta(x)\; \backslash bigr)\; =\; f(x)$, and finally the homomorphism status of $\backslash tilde\{f\}$ implies $\backslash tilde\{f\}(S\_1\; \backslash cup\; S\_2)\; =\; \backslash tilde\{f\}(S\_1)\; \backslash vee\; \backslash tilde\{f\}(S\_2)$ for all $S\_1,S\_2\; \backslash in\; F\_\backslash vee(X)$. Any extension of $\backslash tilde\{f\}$ to infinite subsets of $X$ (if there even is one) need however not be uniquely determined by these conditions, so there cannot in $F\_\backslash vee(X)$ be any elements corresponding to infinite subsets of $X$.

---

Lower semilattices It is similarly possible to define a free functor $F\_\backslash wedge$ for semilattice, but the combination $F\_\backslash wedge(F\_\backslash vee(X))$ fails to produce the free lattice $F(X)$ in several ways, because $F\_\backslash wedge$ treats $F\_\backslash vee(X)$ as just a set:

• the join operation $\backslash vee$ is not extended to the new elements of $F\_\backslash wedge(F\_\backslash vee(X))$,
• the existing partial order on $F\_\backslash vee(X)$ is not respected; $F\_\backslash wedge$ views $a$ and $a\; \backslash vee\; b$ as unrelated, not understanding it should make $a\; \backslash wedge\; (a\; \backslash vee\; b)\; =\; a$.

The actual structure of the free lattice $F(X)$ is considerably more intricate than that of the free semilattice.

---

Word problem

+ Example computation of x∧ z ~ x∧ z∧( x∨ y)
{ style=" border: 1px solid #808080"
		x∧ z
by 5.	since	x∧ z
by 1.	since	x∧ z

|

		x∧ z∧( x∨ y)
by 7.	since	x∧ z	and			x∨ y
by 1.	since	x∧ z		by 6.	since	x
				by 5.	since	x
				by 1.	since	x

|}

The word problem for free lattices has some interesting aspects. Consider the case of bounded lattices, i.e. algebraic structures with the two binary operations ∨ and ∧ and the two constants (nullary operations) 0 and 1. The set of all well-formed expressions that can be formulated using these operations on elements from a given set of generators X will be called W( X). This set of words contains many expressions that turn out to denote equal values in every lattice. For example, if a is some element of X, then a ∨ 1 = 1 and a ∧ 1 = a. The word problem for free bounded lattices is the problem of determining which of these elements of W( X) denote the same element in the free bounded lattice FX, and hence in every bounded lattice.

The word problem may be resolved as follows. A relation ≤_~ on W( X) may be defined inductively by setting w ≤_~ v if and only if one of the following holds:

1.   w = v (this can be restricted to the case where w and v are elements of X),
2.   w = 0,
3.   v = 1,
4.   w = w₁ ∨ w₂ and both w₁ ≤_~ v and w₂ ≤_~ v hold,
5.   w = w₁ ∧ w₂ and either w₁ ≤_~ v or w₂ ≤_~ v holds,
6.   v = v₁ ∨ v₂ and either w ≤_~ v₁ or w ≤_~ v₂ holds,
7.   v = v₁ ∧ v₂ and both w ≤_~ v₁ and w ≤_~ v₂ hold.

This defines a preorder ≤_~ on W( X), so an equivalence relation can be defined by w ~ v when w ≤_~ v and v ≤_~ w. One may then show that the partially ordered Quotient set W( X)/~ is the free bounded lattice FX.Philip M. Whitman, "Free Lattices", Ann. Math. 42 (1941) pp. 325–329Philip M. Whitman, "Free Lattices II", Ann. Math. 43 (1941) pp. 104–115 The equivalence classes of W( X)/~ are the sets of all words w and v with w ≤_~ v and v ≤_~ w. Two well-formed words v and w in W( X) denote the same value in every bounded lattice if and only if w ≤_~ v and v ≤_~ w; the latter conditions can be effectively decided using the above inductive definition. The table shows an example computation to show that the words x∧ z and x∧ z∧( x∨ y) denote the same value in every bounded lattice. The case of lattices that are not bounded is treated similarly, omitting rules 2. and 3. in the above construction.

The solution of the word problem on free lattices has several interesting corollaries. One is that the free lattice of a three-element set of generators is infinite. In fact, one can even show that every free lattice on three generators contains a sublattice which is free for a set of four generators. By induction, this eventually yields a sublattice free on countable many generators.L.A. Skornjakov, Elements of Lattice Theory (1977) Adam Hilger Ltd. (see pp.77-78) This property is reminiscent of SQ-universality in groups.

The proof that the free lattice in three generators is infinite proceeds by inductively defining

p _n+1 = x ∨ ( y ∧ ( z ∨ ( x ∧ ( y ∨ ( z ∧ p _n)))))

where x, y, and z are the three generators, and p₀ = x. One then shows, using the inductive relations of the word problem, that p _n+1 is strictly greaterthat is, p _n ≤_~ p _n+1, but not p _n+1 ≤_~ p _n than p _n, and therefore all infinitely many words p _n evaluate to different values in the free lattice FX.

---

The complete free lattice Another corollary is that the complete free lattice (on three or more generators) "does not exist", in the sense that it is a proper class. The proof of this follows from the word problem as well. To define a complete lattice in terms of relations, it does not suffice to use the finitary relations of meet and join; one must also have infinitary relations defining the meet and join of infinite subsets. For example, the infinitary relation corresponding to "join" may be defined as

$\backslash operatorname\{sup\}\_N:(f:N\backslash to\; FX)$

Here, f is a map from the elements of a Cardinal number N to FX; the operator $\backslash operatorname\{sup\}\_N$ denotes the supremum, in that it takes the image of f to its join. This is, of course, identical to "join" when N is a finite number; the point of this definition is to define join as a relation, even when N is an infinite cardinal.

The axioms of the pre-ordering of the word problem may be adjoined by the two infinitary operators corresponding to meet and join. After doing so, one then extends the definition of $p\_n$ to an ordinal number indexed $p\_\backslash alpha$ given by

when $\backslash alpha$ is a limit ordinal. Then, as before, one may show that $p\_\{\backslash alpha+1\}$ is strictly greater than $p\_\backslash alpha$. Thus, there are at least as many elements in the complete free lattice as there are ordinals, and thus, the complete free lattice cannot exist as a set, and must therefore be a proper class.

• Peter T. Johnstone, Stone Spaces, Cambridge Studies in Advanced Mathematics 3, Cambridge University Press, Cambridge, 1982. () (See chapter 1)

Post Comment